Free monad
fmap と return と join があれば，それはもう実質モナド．
code:haskell
{-# LANGUAGE DeriveFunctor #-} data Free f a
= Pure a -- pure :: Monad m => a -> m a に対応
| Join (f (Free f a)) -- join :: Monad m => m (m a) -> m a に対応
deriving Functor
instance Functor f => Applicative (Free f) where
pure = Pure
Pure a <*> Pure b = Pure $ a b
Pure a <*> Join mb = Join $ fmap a <$> mb
Join ma <*> b = Join $ (<*> b) <$> ma
instance Functor f => Monad (Free f) where
Pure x >>= f = f x
Join x >>= f = Join (fmap (>>= f) x)
与えられた functor を元に自由に生成されるモナドなので，余分な簡約規則が一切ない．そのため，モナドそのものの性質，すなわち「上から下に実行される (前の計算結果に依存して次の計算を行う) プログラム」という性質を純粋に表しており，それゆえ DSL を作るのに向いている． code:haskell
data Free f a
= Pure a -- プログラムの最終行
| Join (f (Free f a)) -- 続きがあるプログラム
code:haskell
-- "Why free monads matter" の例を引用
data Toy b next
= Output b next
| Bell next
| Done
deriving Functor
liftF :: (Functor f) => f r -> Free f r
liftF command = Join (fmap Pure command)
output x = liftF (Output x ())
bell = liftF (Bell ())
done = liftF Done
program :: Free (Toy Int) r
program = do -- Toy 言語用の DSL を獲得した🙌
output 42
bell
done
DSL によって構文木を作ることができたら，それを文字列に変換して pretty print してもよいし，IO に変換して実際に実行してもよい．この言語に対して，後から好きなインタプリタを与えることができる．Free monad によって，言語たるデータとそのインタプリタを分離することができた．
References